class Solution {

    private char[] word1Array = null;
    private char[] word2Array = null;
    private Integer[][] history = null;

    public int minDistance(String word1, String word2) {
        if(word1.equals(word2)){
            return 0;
        }
        word1Array = word1.toCharArray();
        word2Array = word2.toCharArray();
        history = new Integer[word1Array.length][word2Array.length];
        return this.handle(0, 0);
    }

    /**
     * 1/edit, 2/delete, 3/insert
     */
    private int handle(int word1Index, int word2Index){
        int count = 0;
        if (word1Array.length == word1Index && word2Array.length == word2Index){
            return count;
        }
        if (word1Array.length == word1Index){
            // 1结束了，只能插入
            return count + word2Array.length - word2Index;
        }
        if (word2Array.length == word2Index){
            // 2结束了，只能删除
            return count + word1Array.length - word1Index;
        }
        if (history[word1Index][word2Index] != null){
            return history[word1Index][word2Index];
        }
        // 跳过
        if (word1Array[word1Index] == word2Array[word2Index]){
            count = this.handle(word1Index + 1, word2Index + 1);
        } else{
            // 修改
            int updateHandle = this.handle(word1Index + 1, word2Index + 1);
            // 删除
            int deleteHandle = this.handle(word1Index + 1, word2Index);
            // 插入
            int insertHandle = this.handle(word1Index, word2Index + 1);
            count = Math.min(updateHandle, Math.min(deleteHandle, insertHandle))+1;
        }
        history[word1Index][word2Index] = count;
        return count;
    }


}
